1801B - Buying gifts - CodeForces Solution

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

#define T int 
typedef pair<T, T> pii;
typedef tuple<T, T, T> tii;

#define fr first
#define sc second
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define eb emplace_back

#define lowbit(x)    ((x) & -(x))
#define all(x)       (x).begin(), (x).end()
#define rep(i, x, y) for (int i = (x); i <= (y); ++i)
#define per(i, x, y) for (int i = (x); i >= (y); --i)

inline T rd() {
    T x = 0;
    bool f = 0;
    char c = getchar();
    for (; !isdigit(c); c = getchar()) f |= (c == '-');
    for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
    return f ? -x : x;
}

#define N 500007

pii a[N];

int mx[N];

set<int> s;

inline void work() {
	s.clear();
	int n = rd(), ans = 1e9;
	rep(i, 1, n) a[i] = mp(rd(), rd());
	sort(a + 1, a + 1 + n);
	mx[n + 1] = 0;
	per(i, n, 1) mx[i] = max(mx[i + 1], a[i].sc);
	rep(i, 1, n) {
		if (i > 1 && a[i].fr == a[i - 1].fr) s.insert(a[i].sc);
		if (i != n) ans = min(ans, abs(mx[i + 1] - a[i].fr));
		if (mx[i + 1] < a[i].fr && !s.empty()) {
			if (s.lower_bound(a[i].fr) != s.end()) 
				ans = min(ans, *s.lower_bound(a[i].fr) - a[i].fr);
			if (s.lower_bound(a[i].fr) != s.begin())
				ans = min(ans, a[i].fr - *--s.lower_bound(a[i].fr));
		}
		s.insert(a[i].sc);
	}
	printf("%d\n", ans);
}

int main() {
	per(t, rd(), 1) work();
    return 0;
}